Knapsack

Memory limit: 128 MB

Johny and Margaret are leaving for a trip. The boy wanted to impress his friend and decided to pack all their belongings to a single knapsack. Moreover, the heavier the knapsack the better, as it will impress Margaret even more. Obviously Johny cannot pack all the things he has at home, as it could cause the knapsack to tear apart, and such a disaster would make Johny so ashamed that he could never look into Margaret's eyes again.

Furthermore some objects are useless without other objects. Johny has to make sure that, for each object, all objects that it depends on are also taken. For example, if Johny takes a radio, he has to take batteries as well, while taking a tripod enforces taking a camera. For each object Johny determined a different object , such that the object is useless without the object , or he figured out that the object is self-contained and does not require any other object to be taken.

Your task is to help Johny and compute the maximum total weight of all the objects he can take without exceeding the capacity of the knapsack and at the same time without taking any useless object.

Input

The first line of input contains two integers and (, ), describing the number of objects that are under Johny's consideration and the capacity of the knapsack (in kilograms). If one packs objects of total weight exceeding , then the knapsack is going to tear apart.

The objects are numbered through . Each of the following lines contains a description of an object - the -th of those lines contains two integers and (, ), that represent the number of the object the object depends on (if , then the object is self-contained) and the weight of the object in kilograms.

Output

Your program should output a single integer: the maximum total weight (in kilograms) of objects that Johny can take.

Example

For the input data:

7 11
0 3
0 1
2 3
2 2
4 4
5 3
5 2

the correct result is:

10

Task author: Piotr Sankowski.